package demo1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class TreeNode {
    static class Node {
        public char val;
        public Node left;
        public Node right;

        public Node(char val) {
            this.val = val;
        }
    }

    // 根据先序遍历创建二叉树
    static int i = 0;
    public Node createTree(String str) {
        if (str.charAt(i) == '#') {
            i++;
            return null;
        }
        Node node = new Node(str.charAt(i));
        i++;
        node.left = createTree(str);
        node.right = createTree(str);
        return node;
    }
    //中序遍历
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //先序遍历 ---> 遍历思路
    public void preorderTraversal(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal((root.right));
    }
//    public List<Integer> list = new ArrayList<>();
//    public List<Integer> preorderTraversal(TreeNode root) {
//        if (root == null) {
//            return list;
//        }
//        list.add(root.val);
//        preorderTraversal(root.left);
//        preorderTraversal((root.right));
//        return list;
//    }
    //先序遍历 ---> 子问题思路
//public List<Integer> preorderTraversal(TreeNode root) {
//    List<Integer> list = new ArrayList<>();
//    if (root == null) {
//        return list;
//    }
//    list.add(root.val);
//    List<Integer> left = preorderTraversal(root.left);
//    list.addAll(left);
//    List<Integer> right = preorderTraversal(root.right);
//    list.addAll(right);
//    return list;
//}
    //非递归实现先序遍历
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        while (cur != null || !stack.empty()) {
//            if (cur != null) {
//                stack.push(cur);
//                list.add(cur.val);
//                cur = cur.left;
//            } else {
//                cur = stack.pop();
//                cur = cur.right;
//            }
//        }
//        return list;
//    }
    //中序遍历  遍历思路
//List<Integer> list = new ArrayList<>();
//public List<Integer> inorderTraversal(TreeNode root) {
//    if (root == null) {
//        return list;
//    }
//    inorderTraversal(root.left);
//    list.add(root.val);
//    inorderTraversal(root.right);
//    return list;
//}
    //中序遍历 子问题思路
//public List<Integer> inorderTraversal(TreeNode root) {
//    List<Integer> list = new ArrayList<>();
//    if (root == null) {
//        return list;
//    }
//    List<Integer> left = inorderTraversal(root.left);
//    list.addAll(left);
//    list.add(root.val);
//    List<Integer> right = inorderTraversal(root.right);
//    list.addAll(right);
//    return list;
//}
    //中序遍历 ----> 非递归实现
//public List<Integer> inorderTraversal(TreeNode root) {
//    List<Integer> list = new ArrayList<>();
//    TreeNode cur = root;
//    Stack<TreeNode> stack = new Stack<>();
//    while (cur != null || !stack.isEmpty()) {
//        if (cur != null) {
//            stack.push(cur);
//            cur = cur.left;
//        } else {
//            cur = stack.pop();
//            list.add(cur.val);
//            cur = cur.right;
//        }
//    }
//    return list;
//}
    //后序遍历 ---->递归遍历
//public List<Integer> list = new LinkedList<>();
//    public List<Integer> postorderTraversal(TreeNode root) {
//        if (root == null) {
//            return list;
//        }
//        postorderTraversal(root.left);
//        postorderTraversal(root.right);
//        list.add(root.val);
//        return list;
//    }
    //后序遍历 ---> 子问题思路
//public List<Integer> postorderTraversal(TreeNode root) {
//    List<Integer> list = new LinkedList<>();
//    if (root == null) {
//        return list;
//    }
//    List<Integer> left = postorderTraversal(root.left);
//    list.addAll(left);
//    List<Integer> right = postorderTraversal(root.right);
//    list.addAll(right);
//    list.add(root.val);
//    return list;
//}
    //后序遍历 ---> 非递归
//public List<Integer> postorderTraversal(TreeNode root) {
//    List<Integer> list = new LinkedList<>();
//    TreeNode cur = root;
//    Stack<TreeNode> stack = new Stack<>();
//    TreeNode prev = null;
//    while (cur != null || !stack.isEmpty()) {
//        if (cur != null) {
//            stack.push(cur);
//            cur = cur.left;
//        } else {
//            cur = stack.peek();
//            cur = cur.right;
//            if (cur == null || prev == cur) {
//                prev = stack.pop();
//                list.add(prev.val);
//                cur = null;
//            }
//        }
//    }
//
//    return list;
//}


}
